(require (planet schematics/schemeunit:3))

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1) (A x (- y 1))))))

(A 1 10) ; (A (- 1 1) (A 1 (- 10 1)))
(A 0 (A 1 9)) ; (A (- 1 1) (A 1 (- 9 1)))
(A 0 (A 0 (A 1 8))) ; (A (- 1 1) (A 1 (- 8 1)))
(A 0 (A 0 (A 0 (A 1 7)))) ; (A (- 1 1) (A 1 (- 7 1)))
(A 0 (A 0 (A 0 (A 0 (A 1 6))))) ; (A (- 1 1) (A 1 (- 6 1)))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5)))))) ; (A (- 1 1) (A 1 (- 5 1)))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))) ; (A (- 1 1) (A 1 (- 4 1)))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))) ; (A (- 1 1) (A 1 (- 3 1)))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))) ; (A (- 1 1) (A 1 (- 2 1)))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))) ; 2
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))) ; (* 2 2)
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4)))))))) ; (* 2 4)
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))) ; (* 2 8)
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))) ; (* 2 16)
(A 0 (A 0 (A 0 (A 0 (A 0 32))))) ; (* 2 32)
(A 0 (A 0 (A 0 (A 0 64)))) ; (* 2 64)
(A 0 (A 0 (A 0 128))) ; (* 2 128)
(A 0 (A 0 256)) ; (* 2 256)
(A 0 512) ; (* 2 512)
1025 ; Opa, (A 1 n) é 2^n!

(A 2 4) ; (A (- 2 1) (A 2 (- 4 1)))
(A 1 (A 2 3)) ; (A (- 2 1) (A 2 (- 3 1)))
(A 1 (A 1 (A 2 2))) ; (A (- 2 1) (A 2 (- 2 1)))
(A 1 (A 1 (A 1 (A 2 1)))) ; 2
(A 1 (A 1 (A 1 2))) ; (A 1 2) é 2^2
(A 1 (A 1 4)) ; (A 1 4) é 2^4
(A 1 16) ; (A 1 16) é 2^16
65536 ; Hmmm...

(A 3 3) ; (A (- 3 1) (A 3 (- 3 1)))
(A 2 (A 3 2)) ; (A (- 3 1) (A 3 (- 2 1)))
(A 2 (A 2 (A 3 1))) ; 2
(A 2 (A 2 2)) ; (A (- 2 1) (A 2 (- 2 1)))
(A 2 (A 1 (A 2 1))) ; 2
(A 2 (A 1 2)) ; (A 1 2) é 2^2
(A 2 4) ; Da avaliação anterior
65536 ; Hmmm...

; Para n > 0

; f(n) = 2*n
(define (f n) (A 0 n))
(check-equal? (f 2) (* 2 2))
(check-equal? (f 3) (* 2 3))
(check-equal? (f 14) (* 2 14))

; g(n) = 2^n
(define (g n) (A 1 n))
(check-equal? (g 2) (expt 2 2))
(check-equal? (g 4) (expt 2 4))
(check-equal? (g 16) (expt 2 16))

; h(n) =
;       2           se (= n 1)
;       2^(h(n-1))  caso contrário
; Veja que isso cresce de maneira absurda!
(define (h x) (A 2 x))
(check-equal? (h 1) 2)
(check-equal? (h 2) (expt 2 (h 1)))
(check-equal? (h 3) (expt 2 (h 2)))
(check-equal? (h 4) (expt 2 (h 3)))
